#include <cstdio>
#include <ctime>
#include <algorithm>
using namespace std;
typedef struct node
{
    int weight, height; //结点权重以及高度
    struct node *lchild;
    struct node *rchild;
    node()
    {
        weight = 0;
        height = 1;
        lchild = rchild = NULL;
    }
    // node(int w, int h) : weight(w), height(h)
    // {
    // }
} nod_t;
nod_t *create_node(int v)
{
    nod_t *new_nod = new node;
    new_nod->height = 1;
    new_nod->weight = v;
    new_nod->lchild = new_nod->rchild = NULL;
    return new_nod;
}
int get_height(nod_t *root)
{//获取高度
    if (NULL == root)//空结点高度返回零，避免访问空指针导致segment fault
        return 0;
    else
        return root->height;
}
int get_balance_factor(nod_t nod)
{ //获取当前结点的平衡因子
    return get_height(nod.lchild)- get_height(nod.rchild);
}
void update_height(nod_t *root)
{
    root->height = max(get_height(root->lchild), get_height(root->rchild)) + 1;
}
void left_rotate(nod_t *&root)//这里必须要用引用，因为要改变root指针的指向
{ //左旋操作***************
    nod_t *tmp = root->rchild;
    root->rchild = tmp->lchild;
    tmp->lchild = root;
    update_height(root);
    update_height(tmp);
    //*****************
    root = tmp; //更新根节点
}
void right_rotate(nod_t *&root)
{ //右旋操作
    nod_t *tmp = root->lchild;
    root->lchild = tmp->rchild;
    tmp->rchild = root;
    update_height(root);
    update_height(tmp);
    root = tmp;
}
void insert(nod_t *&root, nod_t *new_nod)
{
    if (NULL == root)
    {
        root = new_nod;
    }
    else
    {
        if (new_nod->weight < root->weight)
        { //插入节点比根节点小
            //这里只可能进行LL、LR调整
            insert(root->lchild, new_nod);
            //*****************
            update_height(root); //每次插入都应该更新树高
        }
        else
        { //插入结点比根节点大
            //这里只可能进行RR、RL调整
            insert(root->rchild, new_nod);
            update_height(root); //每次插入都应该更新树高
        }
        //平衡调整
        if (2 == get_balance_factor(*root))
        {//LL,LR
            if (1 == get_balance_factor(*root->lchild))
            {//LL
                right_rotate(root);
            }
            else//LR
            {
                left_rotate(root->lchild);
                right_rotate(root);
            }
        }
        else if (-2 == get_balance_factor(*root))
        {//RR,RL
            if (-1 == get_balance_factor(*root->rchild))
            {//RR
                left_rotate(root);
            }
            else//RL
            {
                right_rotate(root->rchild);
                left_rotate(root);
            }
        }
    }
}
void inorder(nod_t *root)
{
    if (NULL == root)
    {
        return;
    }
    inorder(root->lchild);
    printf("%d ", root->weight);
    inorder(root->rchild);
}
int main()
{
    time_t now = time(NULL); //获取当前时间
    nod_t *root = (nod_t *)malloc(sizeof(nod_t));
    root = NULL;
    int N;
    scanf("%d", &N);
    srand(now);
    while (N--)
    {
        nod_t *new_nod = new node;//new关键字，为节点分配空间的同时，调用构造函数进行初始化
        //new_nod->weight = rand() % 100;
        new_nod->weight = N;
        insert(root, new_nod);
    }
    inorder(root);
    putchar('\n');
    return 0;
}